package com.sourcetrip.my;

import com.sourcetrip.my.abs.AbstractMap;
import com.sourcetrip.my.inter.functional.SelfBalancedTree;
import com.sourcetrip.my.modle.RedBlackNode4Map;
import com.sourcetrip.my.modle.TreeNode;
import com.sourcetrip.utils.MapVisitor;
import com.sourcetrip.utils.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/12/24
 * @description: TreeMapV0 由于之前尝试了分别通过 List 和 RedBlackTree 实现 Set ,从效率上看，红黑树实现的 TreeSet 好了太多。
 * 于是这里直接使用 红黑树 来实现 TreeMapV0
 * --
 * TreeMapV0 使用前提：元素 key 必须具备可比较性（正是由于需要比较，所以 key != null）
 * TODO:记住一个原则- null 可以用于 equals() 但是不能用于 compare(一般)
 * --
 * 设计分析：
 * 1.思考节点：节点继承了红黑树，在每个节点里面保存一个变量用来记录 Value;
 * 至于为何不把整个 k,v 当做一个固定的数据结构进行存储，可能是因为结构比较复杂吧。
 * 2.不是通过组合，而是基于红黑树的结构，重新实现一遍。(其实有大量的工作照搬 二叉搜索树)
 * (不过照搬一次也可以，毕竟是映射，可以不具备树的接口)
 * --
 * 关于改进：
 * 1.由于红黑树中的添加和删除都利用了递归，所以为了防止 StackOverFlow 的情况出现，最好是使用循环。
 * 2.可以将查找节点的部分抽象为一个 node();
 * 3.afterRemove() 参数可以少“旧值”
 * --
 * 由于 TreeMap 中的 key 部分就是 TreeSet ,所以 TreeMap 是包含 TreeSet 的，所以 TreeSet 可以用 TreeMap 实现.
 * 而且在 jdk 中就是用 TreeMap 实现的！
 */
public class TreeMapV0<K, V> extends AbstractMap<K, V> implements SelfBalancedTree<K>, BinaryTreeInfo {

	/**
	 * copy
	 * 照搬 二叉搜索树的 比较器
	 */
	private Comparator<K> comparator;


	//region	constructor

	public TreeMapV0(Comparator<K> comparator) {
		this.comparator = comparator;
	}

	public TreeMapV0() {
	}

//endregion



	/**
	 * copy
	 * 从二叉搜索树开始拷贝
	 * --
	 * 如果 key 已经存在 -> 返回 old value
	 *
	 * @param key
	 * @param value
	 * @return	old value
	 */
	@Override
	public V put(K key, V value) {
		elementNotNullCheck(key);
		if (size == 0) {
			root = createNode(key, value, null);
			//new TreeNode<>(element, null);
			size++;
			//add 修复
			afterAdd(root);
			return value;
		}

		RedBlackNode4Map<K, V> cur = root;
		RedBlackNode4Map<K, V> prev = null;
		while (cur != null) {
			int compare = compare(key, cur.element);
			//如果 相等，将元素进行替换,并返回 old value
			if (compare == 0) {
				V oldValue = cur.value;
				//替换原来的 key
				cur.element = key;
				//替换原来的 value
				cur.value = value;
				return oldValue;
			}
			prev = cur;
			if (compare > 0) {
				cur = (RedBlackNode4Map<K, V>) cur.right;
			} else {
				cur = (RedBlackNode4Map<K, V>) cur.left;
			}
		}

		//此时找到了 prev 就是 所要添加节点的父节点
		RedBlackNode4Map<K, V> node = createNode(key, value, prev);
		int compare = compare(key, prev.element);
		if (compare > 0) {
			prev.right = node;
		} else {
			prev.left = node;
		}
		size++;
		afterAdd(node);
		return value;
	}

	/**
	 * 根据 key 获得 value
	 * 如果 没有对应的 key 就返回 null
	 *
	 * @param key
	 * @return
	 */
	@Override
	public V get(K key) {
		elementNotNullCheck(key);
		RedBlackNode4Map<K, V> cur = root;
		RedBlackNode4Map<K, V> prev = null;
		while (cur != null) {
			int compare = compare(key, cur.element);
			//如果 相等，将元素进行替换,并返回 old value
			if (compare == 0) {
				return cur.value;
			}
			prev = cur;
			if (compare > 0) {
				cur = (RedBlackNode4Map<K, V>) cur.right;
			} else {
				cur = (RedBlackNode4Map<K, V>) cur.left;
			}
		}
		//没有找到 返回 null
		return null;
	}


	/**
	 * 移除
	 *
	 * @param key
	 * @return
	 */
	@Override
	public V remove(K key) {
		return remove(root, key, null);
	}

	/**
	 * 是否包含 key 元素
	 *
	 * @param key
	 * @return
	 */
	@Override
	public boolean containsKey(K key) {
		elementNotNullCheck(key);
		RedBlackNode4Map<K, V> cur = root;
		RedBlackNode4Map<K, V> prev = null;
		while (cur != null) {
			int compare = compare(key, cur.element);
			//如果 相等，找到了 元素，返回 true
			if (compare == 0) {
				return true;
			}
			prev = cur;
			if (compare > 0) {
				cur = (RedBlackNode4Map<K, V>) cur.right;
			} else {
				cur = (RedBlackNode4Map<K, V>) cur.left;
			}
		}
		//没有找到 返回 null
		return false;
	}

	/**
	 * 由于 value  并没有按照二叉搜索树的规则，所以只能遍历！
	 * 说明了 containsValue 的效率低下！
	 * 就用层序遍历好了
	 *
	 * @param value
	 * @return
	 */
	@Override
	public boolean containsValue(V value) {
		Queue<RedBlackNode4Map<K, V>> queue = new LinkedList<>();
		queue.offer(root);
		if (value == null) {
			//
			while (!queue.isEmpty()) {
				RedBlackNode4Map<K, V> cur = queue.poll();
				//进行匹配
				if (cur.value == null) {
					return true;
				}
				if (cur.left != null) {
					queue.offer((RedBlackNode4Map<K, V>) cur.left);
				}
				if (cur.right != null) {
					queue.offer((RedBlackNode4Map<K, V>) cur.right);
				}
			}
		} else {
			//非 null 的判断
			while (!queue.isEmpty()) {
				RedBlackNode4Map<K, V> cur = queue.poll();
				//进行匹配
				if (value.equals(cur.value)) {
					return true;
				}
				if (cur.left != null) {
					queue.offer((RedBlackNode4Map<K, V>) cur.left);
				}
				if (cur.right != null) {
					queue.offer((RedBlackNode4Map<K, V>) cur.right);
				}
			}
		}
		return false;
	}

	/**
	 * 相应的，通过 key 从小到大进行排序 => inorder
	 * 左，根，右
	 * TODO:过了几天之后又靠自己写出来了一个写法，总结一下有两点：
	 * 1.保证循环体中一个流程中只会处理一下（基本上是这样的）；
	 * 2.三种遍历方式中都会有一个找到最左边元素的写法！
	 *
	 * @param visitor
	 */
	@Override
	public void traversal(MapVisitor<K, V> visitor) {
		Stack<RedBlackNode4Map<K, V>> stack = new Stack<>();
		stack.push(root);
		RedBlackNode4Map<K, V> cur = null;
		boolean visitedLeft = false;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null && !visitedLeft) {
				stack.push(cur);
				cur = (RedBlackNode4Map<K, V>) cur.left;
			}
			//leftest
			//visit node
			if (!visitor.stop) {
				visitor.visit(cur.element, cur.value);
			}
			if (cur.right != null) {
				stack.push((RedBlackNode4Map<K, V>) cur.right);
				visitedLeft = false;
			} else {
				visitedLeft = true;
			}
		}
	}


	//region	private methods

	/**
	 * 从 node 开始删除 K=key 的节点
	 *
	 * @param node
	 * @param key
	 * @param oldValue 旧值（其实可以不用传这个，因为可以将递归部分的返回值忽略即可！）
	 * @return
	 */
	private V remove(RedBlackNode4Map<K, V> node, K key, V oldValue) {
		elementNotNullCheck(key);
		//根节点 为空，直接返回
		if (node == null) {
			return null;
		}
		RedBlackNode4Map<K, V> cur = node;
		while (cur != null) {
			int compare = compare(key, cur.element);
			if (compare == 0) {
				//找到删除的元素
				break;
			}
			if (compare > 0) {
				cur = (RedBlackNode4Map<K, V>) cur.right;
			} else {
				cur = (RedBlackNode4Map<K, V>) cur.left;
			}
		}
		if (cur == null) {
			//此时没有找到元素，直接返回
			return null;
		}

		RedBlackNode4Map<K, V> parent = (RedBlackNode4Map<K, V>) cur.parent;
		//此时 cur == 要删除的元素
		if (cur.left == null && cur.right == null) {
			//如果是 叶子节点
			if (parent != null) {
				if (cur.isLeftChild()) {
					parent.left = null;
				} else {
					parent.right = null;
				}
			} else {
				//TODO:忽略了 根节点元素的处理
				root = null;
			}
			//删除之后的修复
			//afterRemove(cur);
			afterRemove(cur, null);
			//真正进行删除，需要判断是否属于递归中的
			oldValue = oldValue == null ? cur.value : oldValue;
		} else if (cur.left != null && cur.right != null) {
			//如果是 度 == 2
			//1.找到 前驱/后继节点
			RedBlackNode4Map<K, V> predecessor = predecessor(cur);
			//2.用 前驱/后继节点 的 ele 替换 cur
			cur.element = predecessor.element;
			//3.删除 前驱/后继节点
			remove((RedBlackNode4Map<K, V>) cur.left, cur.element, cur.value);
			//此处没有真正的删除，不做修复
		} else if (cur.left != null) {
			//度 == 1 && 左节点不为空
			if (parent != null) {
				if (cur.isLeftChild()) {
					parent.left = cur.left;
				} else {
					parent.right = cur.left;
				}
			}
			//处理 node.left 的父节点
			cur.left.parent = parent;
			//删除之后的修复
			//afterRemove(cur);
			afterRemove(cur, (RedBlackNode4Map<K, V>) cur.left);

			oldValue = oldValue == null ? cur.value : oldValue;
		} else {
			//度 == 1 && 右节点不为空
			if (parent != null) {
				if (cur.isLeftChild()) {
					parent.left = cur.right;
				} else {
					parent.right = cur.right;
				}
			}
			cur.right.parent = parent;

			//删除之后的修复
			//afterRemove(cur);
			afterRemove(cur, (RedBlackNode4Map<K, V>) cur.right);

			oldValue = oldValue == null ? cur.value : oldValue;
		}
		size--;
		return oldValue;
	}


	/**
	 * copy
	 * 由于元素具备可比较性，所以必须排除 null !
	 *
	 * @param key
	 */
	private void elementNotNullCheck(K key) {
		if (key == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}

	/**
	 * copy
	 *
	 * @param e1
	 * @param e2
	 * @return
	 */
	private int compare(K e1, K e2) {
		int res = 0;
		try {
			res = (comparator != null) ? comparator.compare(e1, e2) : ((Comparable) e1).compareTo(e2);
		} catch (Exception e) {
			throw new RuntimeException("元素比较发生了异常！");
		} finally {
			return res;
		}
	}

	/**
	 * 获取节点的父节点
	 *
	 * @param node
	 * @return
	 */
	private RedBlackNode4Map<K, V> getParentNode(RedBlackNode4Map<K, V> node) {
		return (RedBlackNode4Map<K, V>) node.parent;
	}

	/**
	 * @param node
	 */
	private void setNodeBlack(RedBlackNode4Map<K, V> node) {
		((RedBlackNode4Map<K, V>) node).black();
	}

	private void setNodeRed(RedBlackNode4Map<K, V> node) {
		((RedBlackNode4Map<K, V>) node).red();
	}

	/**
	 * 判断 节点是否为黑色
	 *
	 * @param node
	 * @return
	 */
	private boolean isNodeBlack(RedBlackNode4Map<K, V> node) {
		return node == null || node.isBlack();
	}

	/**
	 * 判断节点是否为红色
	 *
	 * @param node
	 * @return
	 */
	private boolean isNodeRed(RedBlackNode4Map<K, V> node) {
		return !isNodeBlack(node);
	}

	/**
	 * 获取 叔叔节点
	 *
	 * @param node
	 * @return
	 */
	private RedBlackNode4Map<K, V> getUncleNode(RedBlackNode4Map<K, V> node) {
		if (node == null) {
			return null;
		}
		RedBlackNode4Map<K, V> parent = (RedBlackNode4Map<K, V>) node.parent;
		if (parent == null) {
			return null;
		}
		RedBlackNode4Map<K, V> grandNode = getParentNode(parent);
		if (grandNode == null) {
			return null;
		}
		//此时 parent != null
		if (parent.isRightChild()) {
			return (RedBlackNode4Map<K, V>) grandNode.left;
		} else {
			return (RedBlackNode4Map<K, V>) grandNode.right;
		}
	}

	/**
	 * 获取 兄弟节点
	 * @param node
	 * @return
	 */
	protected RedBlackNode4Map<K, V> getSiblingNode(RedBlackNode4Map<K, V> node) {
		//对于红黑树删除情况，子节点为 null 时即为删除的节点
		RedBlackNode4Map<K, V> parent = (RedBlackNode4Map<K, V>)node.parent;
		if (parent==null){
			return null;
		}
		if (parent.left == null) {
			return (RedBlackNode4Map<K, V>)parent.right;
		}else {
			return (RedBlackNode4Map<K, V>)parent.left;
		}
	}

	/**
	 * 查找前驱节点
	 *
	 * @param node
	 * @return
	 */
	private RedBlackNode4Map<K, V> predecessor(RedBlackNode4Map<K, V> node) {
		if (node == null || node.left == null) {
			return null;
		}
		RedBlackNode4Map<K, V> cur = (RedBlackNode4Map<K, V>) node.left;
		while (cur.right != null) {
			cur = (RedBlackNode4Map<K, V>) cur.right;
		}
		//此时 cur 即 前驱节点
		return cur;
	}

	//endregion

	//region	protected methods

	/**
	 * 创建节点
	 *
	 * @param key
	 * @param value
	 * @param parent
	 * @return
	 */
	protected RedBlackNode4Map<K, V> createNode(K key, V value, RedBlackNode4Map<K, V> parent) {
		return new RedBlackNode4Map<>(key, value, parent);
	}

	/**
	 * 红黑树添加之后的修复
	 *
	 * @param node
	 */
	protected void afterAdd(RedBlackNode4Map<K, V> node) {
		if (node == null) {
			return;
		}
		//如果节点为 1，说明是根节点 -》 直接染色
//		if (size == 1)
//			setNodeBlack(node);
//			return;
//		}
		RedBlackNode4Map<K, V> parentNode = getParentNode(node);
		if (parentNode == null) {
			//由于 上溢 时的递归，于是和 根节点染色进行合并
			setNodeBlack(node);
			return;
		}

		//1.如果挂在 Black Node 之下，直接返回
		if (isNodeBlack(parentNode)) {
			return;
		}
		//获取 uncle 节点(由于 parent.color == RED ,说明 必定存在 grand 节点！)
		RedBlackNode4Map<K, V> uncleNode = getUncleNode(node);
		RedBlackNode4Map<K, V> grandNode = getParentNode(parentNode);
		if (isNodeBlack(uncleNode)) {
			setNodeRed(grandNode);
			//2.parent.color == RED && uncle.color == BLACK (4)
			//可以从图得知，考虑 LL/RR/LR/RL 情况，
			// 并染色，根据上述四种不同的情况有不同的染色方式，最终都是：最高的节点为 BLACK，左右子节点为 RED
			if (parentNode.isLeftChild()) {
				//L
				if (node.isLeftChild()) {
					//LL-> black(p) + red(g)
					rotateRight(grandNode);

					//setNodeRed(grandNode);
					setNodeBlack(parentNode);
				} else {
					//LR-> black(node) + red(g)
					rotateLeft(parentNode);
					rotateRight(grandNode);

					setNodeBlack(node);
				}
			} else {
				//R
				if (node.isLeftChild()) {
					//RL -> 同 LR black(node) + red(g)
					rotateRight(parentNode);
					rotateLeft(grandNode);

					//setNodeRed(grandNode);
					setNodeBlack(node);
				} else {
					//RR -> red(grand)+ black(p)
					rotateLeft(grandNode);

					setNodeBlack(parentNode);
				}
			}
		} else {
			//3.parent.color == RED && uncle.color == RED (4)
			//red(grand) 并作为新节点添加到上面
			//black(parent) + black(uncle) 作为新的根节点
			setNodeBlack(parentNode);
			setNodeBlack(uncleNode);

			setNodeRed(grandNode);

			afterAdd(grandNode);
		}


	}

	/**
	 * 红黑树删除之后的修复
	 *
	 * @param node
	 * @param replacement
	 */
	protected void afterRemove(RedBlackNode4Map<K, V> node, RedBlackNode4Map<K, V> replacement) {
		RedBlackNode4Map<K, V> parentNode = getParentNode(node);
		//1.删除根节点 or 删除节点为红色
		if (parentNode == null || isNodeRed(node)) {
			return;
		}
		//2.replacement is red(此时对于 BST 而言，是度为1)
		if (isNodeRed(replacement)) {
			//将 replacement 染黑 即可
			setNodeBlack(replacement);
			return;
		}
		//3.删除的根节点为 Black && 替代节点为 Black(叶子节点 && 度为 2)
		RedBlackNode4Map<K, V> siblingNode = getSiblingNode(node);
		if (isNodeBlack(siblingNode)) {
			//3.1 兄弟节点为黑色(作为主节点)
			RedBlackNode4Map<K, V> leftSibling = (RedBlackNode4Map<K, V>) siblingNode.left;
			RedBlackNode4Map<K, V> rightSibling = (RedBlackNode4Map<K, V>) siblingNode.right;
			//3.1.1. 不可借，发生下溢
			if (isNodeBlack(leftSibling) && isNodeBlack(rightSibling)) {
				afterRemove(parentNode, null);
				//最后再染色，因为删除的节点的颜色属性需要拿到新的一轮进行判断
				setNodeBlack(parentNode);
				setNodeRed(siblingNode);
				return;
			}
			if (siblingNode.isLeftChild()) {
				//L
				if (isNodeRed(leftSibling)) {
					//LL
					rotateRight(parentNode);

					setNodeBlack(leftSibling);
				} else {
					//LR - 说明 rightSibling is red
					rotateLeft(siblingNode);
					rotateRight(parentNode);

					setNodeBlack(rightSibling);
				}

			} else {
				//R
				if (isNodeRed(rightSibling)) {
					//RR
					rotateLeft(parentNode);

					setNodeBlack(rightSibling);
				} else {
					//RL
					rotateRight(siblingNode);
					rotateLeft(parentNode);

					setNodeBlack(leftSibling);
				}

			}
		} else {
			//3.2 兄弟节点为红色
			if (siblingNode.isLeftChild()) {
				//sibling is left node
				rotateRight(siblingNode);

			} else {
				//sibling is right node

				rotateLeft(siblingNode);
			}
			setNodeBlack(siblingNode);
			setNodeRed(parentNode);
			afterRemove(node, null);
		}

	}

	@Override
	public void afterRotate(TreeNode<K> prev, TreeNode<K> grand, TreeNode<K> parent, TreeNode<K> child) {
		if (prev == null) {
			root = (RedBlackNode4Map<K, V>) parent;
			setNodeBlack(root);
		}
	}



//endregion


}
